using System.Collections;
using System.Collections.Generic;
using UnityEngine;

namespace JufGame
{
	public class Octree
	{
		private const float Accuracy = 1.5f;
		private static readonly Vector3[] neighborDir =
		{
			new(1, 0, 0), new(-1, 0, 0),
			new(0, 1, 0), new(0, -1, 0),
			new(0, 0, 1), new(0, 0, -1)
		};//六个面所对应的方向
		public OctreeNode RootNode;//根节点
		public List<OctreeNode> EmptyLeaves;//空节点列表，即所有没有包含物体的节点
		public MyGraph<OctreeNode, int> NavigationGraph; //节点所构成的图
		private readonly float minNodeSize;
		public Octree(GameObject[] worldObjects, float minNodeSize, MyGraph<OctreeNode, int> navGraph)
		{
			var bounds = new Bounds();
			EmptyLeaves = new List<OctreeNode>();
			NavigationGraph = navGraph;
			this.minNodeSize = minNodeSize;
			foreach(var o in worldObjects)
			{
				bounds.Encapsulate(o.GetComponent<Collider>().bounds);
			}
			var maxSize = Mathf.Max(bounds.size.x, bounds.size.y, bounds.size.z);
			var newCubeSize = 1f * maxSize * Vector3.one;
			bounds.SetMinMax(bounds.center - newCubeSize, bounds.center + newCubeSize);

			RootNode = new OctreeNode(bounds, null);
			AddObject(worldObjects);
			GetEmptyLeaves(RootNode);
			ConnectLeafNeighbor();
		}
		/// <summary>
		/// 以指定节点开始搜索，寻找到与指定位置最接近的节点
		/// </summary>
		/// <param name="start">初始点</param>
		/// <param name="pos">指定位置</param>
		/// <returns>寻找到的节点，若没找到则返回null</returns>
		public OctreeNode GetNodeByPos(OctreeNode start, Vector3 pos)
		{
			OctreeNode findNode = null;
			if (start == null) 
				return findNode;
			if (start.Children == null)
			{
				if(start.NodeBounds.Contains(pos))
					return start;
			}
			else
			{
				for(int i = 0; i < 8; ++i)
				{
					findNode = GetNodeByPos(start.Children[i], pos);
					if (findNode != null)
						return findNode;
				}				
			}
			return findNode;
		}
		private void AddObject(GameObject[] worldObjects)
		{
			foreach(var o in worldObjects)
			{
				RootNode.AddObject(o, minNodeSize);
			}
		}
		private void GetEmptyLeaves(OctreeNode node)
		{
			if (node == null) return;
			if(node.Children == null && node.ContainedObjects.Count == 0)
			{
				EmptyLeaves.Add(node);
				NavigationGraph.AddNode(node);
			}
			if(node.Children != null)
			{
				for(int i = 0; i < node.Children.Count; ++i)
				{
					var c = node.Children[i];
					GetEmptyLeaves(c);
				}
			}
		}
		private void ConnectLeafNeighbor()
		{
			for(int i = 0; i < EmptyLeaves.Count; ++i)
			{
				for(int j = 0; j < EmptyLeaves.Count; ++j)
				{
					if (i == j || EmptyLeaves[j].NodeBounds.size.x == minNodeSize) continue;
					for(int r = 0; r < neighborDir.Length; ++r)
					{
						var ray = new Ray(EmptyLeaves[i].NodeBounds.center, neighborDir[r]);
						var maxLength = EmptyLeaves[i].NodeBounds.size.y / 2.0f + 0.01f;
						if(EmptyLeaves[j].NodeBounds.IntersectRay(ray, out float hitLength))
						{
							if(hitLength < maxLength)
							{
								NavigationGraph.AddEdge(EmptyLeaves[i], EmptyLeaves[j], 1);
								NavigationGraph.AddEdge(EmptyLeaves[j], EmptyLeaves[i], 1);
							}
						}
					}
				}
			}
			Debug.Log(NavigationGraph.EdgeList.Count);
		}
	}
}
